package test.app;

import test.graph.Graph2;
import test.huihui.MyBinaryTree;
import test.huihui.MyLinkedList;
import test.huihui.MyQueue;
import test.huihui.PriorityQueue2;
import test.huihui.sort.bucketSort;
import test.huihui.sort.countSort;
import test.huihui.sort.quickSort;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;
import test.labuladong.feibolaqie;
import test.labuladong.kmp;
import model.ColorNode;
import model.ListNode;
import test.queue.MonotonicQueue;
import test.sort.HeapSort;
import test.sort.MergeSort;
import test.sort.QuickSort;
import test.tree.Heap;
import test.tree.UF;
import test.tree.wordTrie;

public class App {

  public static void main(String[] args) throws Exception {
    //strStr("", "");

    //String r345 = new App().reverseWords2("a good   example");
    //int res3 = new App().compareVersion("0.1", "1.1");

    // int r232 = new App().jump(new int[] { 2, 3, 1, 1, 4 });
    // int r233 = new App()
    //     .maxSubArray(new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 });

    // int[][] matrix = new int[][] { {1,3,5,7 }, { 10,11,16,20}, { 23,30,34,60} };
    // int rowIndex = new App().binarySearchFirstColumn(matrix, 3);

    // new App().sortColors(new int[] { 2, 0, 2, 1, 1, 0 });

    // new App().largestRectangleArea2(new int[] { 2, 1, 5, 6, 2, 3 });

    // char[][] matrix = {
    //     { '1', '0', '1', '0', '0' },
    //     { '1', '0', '1', '1', '1' }, 
    //     { '1', '1', '1', '1', '1' }, 
    //     { '1', '0', '0', '1', '0' } ,
    // };
    // new App().maximalRectangle(matrix);

    // new App().merge(new int[0], 0, new int[] { 1 }, 1);
//
//    List<List<Integer>> triangle = new ArrayList<>();
//    List<Integer> row1 = new ArrayList<Integer>(Arrays.asList(new Integer[] { 2 }));
//    List<Integer> row2 = new ArrayList<Integer>(Arrays.asList(new Integer[] { 3, 4 }));
//    List<Integer> row3 = new ArrayList<Integer>(Arrays.asList(new Integer[] { 6, 5, 7 }));
//    List<Integer> row4 = new ArrayList<Integer>(Arrays.asList(new Integer[] { 4, 1, 8, 3 }));
//    triangle.add(row1);
//    triangle.add(row2);
//    triangle.add(row3);
//    triangle.add(row4);
//    int r334 = new App().minimumTotal(triangle);

    // new csNote.Sort.SelectionSort()
    // .sort(new Integer[] { 10, 9, 2, 5, 3, 7, 101, 18 });
    // new csNote.Sort.BubbleSort()
    // .sort(new Integer[] { 10, 9, 2, 5, 3, 7, 101, 18 });
    // new csNote.Sort.InsertionSort()
    // .sort(new Integer[] { 10, 9, 2, 5, 3, 7, 101, 18 });
    // new csNote.Sort.ShellSort()
    // .sort(new Integer[] { 10, 9, 2, 5, 3, 7, 101, 18 });
    // new csNote.Sort.Up2DownMergeSort()
    // .sort(new Integer[] { 10, 9, 2, 5, 3, 7, 101, 18 });
    // new csNote.Sort.QuickSort()
    // .sort(new Integer[] { 10, 9, 2, 5, 3, 7, 101, 18 });

    // String s33 = reverseWords("Let's take LeetCode contest");
    // String s22 = "abcdefg";
    // String temp33 = reverseStr(s22, 2);

    // int t_6 = longestValidParentheses2("()");

    // // 解法1：递归
    // int[] nums = new int[] { 10, 9, 2, 5, 3, 7, 101, 18 };
    // int[][] memo = new int[nums.length + 1][nums.length];
    // for (int[] item : memo) {
    //   Arrays.fill(item, -1);
    // }
    // int t_5 = lengthOfLIS(nums, -1, 0, memo);

    // int[] t_4 = relativeSortArray(
    //   new int[] { 2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19 },
    //   new int[] { 2, 1, 4, 3, 9, 6 }
    // );
    // int t_3 = reverseBits(43261596);
    // sss2();

    // int t_23 = 1 / 3;
    // for (int i = 0; i < 9; i++) {
    //   for (int j = 0; j < 9; j++) {
    //     int box = (i / 3) * 3 + j / 3;
    //     System.out.println("i:" + i + ",j:" + j + ",box:" + box);
    //   }
    // }
    // TrieNode trie2 = buildTrie(new String[] { "oath", "pea", "eat", "rain" });

    // int r_4 = leastInterval(new char[] { 'A', 'A', 'A', 'B', 'B', 'B' }, 2);
    // int r_3 = numDecodings("12");

    // String word1 = "horse", word2 = "ros";
    // int ttt2 = minDistance(word1, word2);
    // int r_1 = largestRectangleArea(new int[] { 2, 1, 5, 6, 2, 3 });
    // int[] r_2 = maxSlidingWindow(new int[] { 1, 3, -1, -3, 5, 3, 6, 7 }, 3);

    // List<String> r388 = generateParenthesis(3);

    // ListNode head1 = new ListNode(1);
    // head1.next = new ListNode(2);
    // head1.next.next = new ListNode(4);

    // ListNode head2 = new ListNode(1);
    // head2.next = new ListNode(3);
    // head2.next.next = new ListNode(4);
    // ListNode r4 = mergeTwoLists(head1, head2);

    // ListNode head = new ListNode(1);
    // head.next = new ListNode(2);
    // head.next.next = new ListNode(3);
    // head.next.next.next = new ListNode(4);
    // head.next.next.next.next = new ListNode(5);
    // ListNode r3 = reverseKGroup2(head, 2);

    // ListNode temp = head;
    // temp.val = 3;
    // temp = temp.next;

    // //解法2：迭代
    // ListNode temp=head;
    // int index=0;
    // while(temp!=null){
    //     if(index%2==0 && temp.next!=null){
    //         int val=temp.val;
    //         temp.val=temp.next.val;
    //         temp.next.val=val;
    //     }
    //     temp=temp.next;
    //     index++;
    // }

    // int tdd = findKthLargest(new int[] { 3, 2, 1, 5, 6, 4 }, 2);

    // String s1 = "abc";
    // String s2 = "bac";
    // char[] c11 = s1.toCharArray();
    // char[] c12 = s2.toCharArray();
    // Arrays.sort(c11);
    // Arrays.sort(c12);
    // boolean s34 = String.valueOf(c11).equals(String.valueOf(c12));
    // String s_1 = "abab";
    // String s_2 = "ab";
    // List<Integer> i233 = findAnagrams(s_1, s_2);

    // int ssfs = longestValidParentheses("()");

    // Map<Integer, Integer> map222 = new TreeMap();
    // map222.put(1, 2);
    // map222.put(0, 0);
    // Set<Entry<Integer, Integer>> dd = map222.entrySet();
    // Set<Integer> keyset = map222.keySet();
    // for (int n : map222.keySet()) {}
    // String aaa2 = "abc";
    // String baaa = change(aaa2, 1, 2);

    // char[][] board = new char[9][9];
    // board[0][0] = 9;
    // board[0][1] = 3;
    // App.isValidSudoku(board);

    // UF uf = new UF(3);
    // uf.union(0, 0);
    // uf.union(0, 1);
    // uf.union(2, 2);

    // LinkedList<Integer> list3 = new LinkedList<>();
    // list3.add(1);
    // list3.add(2);
    // list3.add(1);

    // Integer ddd3 = list3.remove(1);

    // wordTrie trie = new wordTrie();
    // trie.insert("oath");
    // trie.insert("pea");
    // trie.insert("eat");
    // trie.insert("rain");

    // MonotonicQueue monotonicQueue = new MonotonicQueue();
    // monotonicQueue.push(1);
    // monotonicQueue.push(2);
    // monotonicQueue.push(3);
    // monotonicQueue.push(4);
    // monotonicQueue.push(4);
    // monotonicQueue.push(3);
    // monotonicQueue.push(2);
    // monotonicQueue.push(1);

    // int m1 = monotonicQueue.max();
    // monotonicQueue.pop(4);

    // ListNode l = new ListNode(1);
    // l.next = new ListNode(2);
    // l.next.next = new ListNode(3);
    // l.next.next.next = new ListNode(4);
    // l.next.next.next.next = new ListNode(5);
    // l.next.next.next.next.next = new ListNode(6);

    // ListNode lll = reverseBetween(l, 2, 4);
    // int[] nums2 = new int[] { 3, 0, 1, 4, 5 };
    // int rrr = MissNumber(nums2);
    // int aaa = 27 % 10;
    // int bbb = 15 / 10;
    // int ccc = 4 ^ 4 ^ 4 ^ 4;

    // Character c2 = ('b' | ' ');
    // Character c3 = ('B' | ' ');

    // Character c4 = ('b' & '_');
    // Character c5 = ('B' & '_');

    // Arrays.asList("Hello", "Java8", "Java7").stream().map(s -> s.toUpperCase());

    // int[] commands = new int[] { 4, -1, 3 };
    // int[][] obstacles = new int[0][0];
    // int rob = App.robotSim(commands, obstacles);

    // int sum = new feibolaqie().feb(10);
    // int sum2 = new feibolaqie().feb2(10);
    // int sum3 = new feibolaqie().feb3(10);
    // int sum4 = new feibolaqie().feb4(10);

    // int searIndex = new kmp("cab").search("abcabc");

    // double[] tte2 = bucketSort.bucketSort2(
    //   new double[] { 1.3, 23, 55, 2.4, 3 }
    // );
    // int[] ttt = countSort.countSort2(new int[] { 1, 23, 55, 2, 3 });

    // char[][] board = new char[4][4];
    // for (char[] chars : board)
    //     Arrays.fill(chars, '.');

    // boolean b = new App().isValid(board, 0, 0);

    // String next_digits = "DV";
    // String digit = next_digits.substring(0, 1);
    // String digit2 = next_digits.substring(0);

    // List<List<Integer>> output = new ArrayList();
    // for (int k = 0; k < nums.length + 1; ++k) {
    //     backtrack(k, 0, new ArrayList<Integer>(), nums, output);
    // }

    // int[] preorder = new int[] { 3, 9, 20, 15, 7 };
    // int[] inorder = new int[] { 9, 3, 15, 20, 7 };
    // TreeNode r = new App().buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);

    // MyBinaryTree binaryTree = new MyBinaryTree();
    // int[] arr = new int[] { 1, 3, 2, 6, 5, 7, 8, 9, 10, 0 };
    // binaryTree.upAdjust(arr);

    // int[] arr2 = new int[] { 7, 1, 3, 10, 5, 2, 8, 9, 6 };
    // binaryTree.buildHeap(arr2);

    // PriorityQueue priorityQueue = new PriorityQueue();
    // priorityQueue.enQueue(10);
    // priorityQueue.enQueue(5);
    // priorityQueue.enQueue(3);
    // priorityQueue.enQueue(2);
    // priorityQueue.enQueue(7);

    // priorityQueue.deQueue();
    // priorityQueue.deQueue();

    // MyLinkedList list = new MyLinkedList();
    // list.insert(1, 0);
    // list.insert(2, 1);
    // list.insert(3, 2);
    // list.oupPut();

    // MyQueue myQueue = new MyQueue(5);
    // myQueue.enQueue(1);
    // myQueue.enQueue(2);
    // myQueue.enQueue(3);
    // myQueue.enQueue(4);
    // myQueue.deQueue();
    // myQueue.deQueue();
    // myQueue.outPut();

    // Integer[] arrTemp = new Integer[] { 3, 2, 9, null, null, 10, null, null, 8, null, 4 };
    // LinkedList<Integer> linkedList = new LinkedList<>(Arrays.asList(arrTemp));
    // MyBinaryTree myBinaryTree = new MyBinaryTree();
    // TreeNode treenode = myBinaryTree.createBinaryTree(linkedList);
    // System.out.println("前序遍历：");
    // MyBinaryTree.preOrderTraversal(treenode);

    // StringBuilder cur=new StringBuilder();
    // cur.append("1234");
    // cur.deleteCharAt(cur.length() - 1);

    // LinkedList<Integer> queue = new LinkedList<>();//双端队列

    // queue.push(11);
    // queue.push(22);
    // queue.pop();

    // queue.add(1);
    // queue.add(2);
    // int ttt = queue.peek();//获取下标=0的值

    // queue.add(11);
    // boolean b23 = queue.add(22);//尾部添加
    // boolean b33 = queue.offer(44);//尾部添加
    // queue.push(33);//头部添加

    // queue.pop();
    // queue.remove();//移除头部
    // queue.poll();//移除头部

    // int t2 = queue.poll();

    // TreeNode root = new TreeNode(1);
    // root.left = new TreeNode(2);
    // root.left.left = new TreeNode(4);
    // root.left.right = new TreeNode(5);

    // List<Integer> listsss = new App().preorderTraversal(root);

    // App app = new App();
    // app.push(1);
    // app.push(2);
    // app.push(3);

    // App app2 = new App();
    // app2.push2(1);
    // app2.push2(2);
    // app2.push2(3);

    // boolean bb = new App().isValid2("(]");

    // int[] fun = { 0, 1, 2, 3, 4, 5, 6 };
    // System.arraycopy(fun, 0, fun, 2, 4);

    // int a = (~5);
    // int b = (456 >> 1) & 1;
    // boolean b1 = (12 & 1) == 1;

    // int c = 12 & 12;

    // Heap heap = new Heap(10);
    // heap.insert(2);
    // heap.insert(1);
    // heap.insert(6);
    // heap.insert(9);
    // heap.removeMax();

    // Graph2 graph2 = new Graph2(8);
    // graph2.addEdge(0, 1);
    // graph2.addEdge(0, 3);

    // graph2.addEdge(1, 2);
    // graph2.addEdge(1, 4);

    // graph2.addEdge(2, 5);

    // graph2.addEdge(3, 4);

    // graph2.addEdge(4, 5);
    // graph2.addEdge(4, 6);

    // graph2.addEdge(5, 7);

    // graph2.addEdge(6, 7);

    // // graph2.bfs(0, 6);

    // graph2.dfs(0,6);

    // int[] arr = new int[] { 1, 3, 2, 4, 5 };
    // int result = new MergeSort().count(arr, 5);
    // System.out.println(result);

    // ListNode node = new ListNode(1);
    // node.next = new ListNode(2);

    // node.next.next = new ListNode(3);
    // node.next.next.next = new ListNode(4);
    // node.next.next.next.next = new ListNode(5);

    // //ListNode nodeResult = new App().swapPairs(node);
    // ListNode nre = new App().reverseKGroup(node, 3);

    //boolean b=new App().isValid("()[]");

    // TreeNode root = new TreeNode(1);
    // root.left = new TreeNode(2);
    // root.left.left = new TreeNode(3);
    // root.left.right = new TreeNode(4);

    // List<Integer> result333=new App().inorderTraversal(root);

    // TreeNode root2 = new TreeNode(4);
    // root2.left = new TreeNode(2);
    // root2.left.left = new TreeNode(13);
    // root2.left.right = new TreeNode(3);

    // boolean bll = new App().helper2(root2, null, null);

    // double mypow = new App().myPow(1.1, 3);

    // int[] nums = new int[] { 1, 2, 3 };
    // List<List<Integer>> list2 = new App().subsets(nums);

    // int greatestCommonDivisor = getGreatestCommonDivisor2(10, 25);

    // int n = 5;
    // int w = 10;
    // int[] g = new int[] { 500, 400, 350, 300, 200 };
    // int[] p = new int[] { 5, 5, 3, 4, 3 };
    // int result = getMostGold(n, w, g, p);

    // int x = 1;
    // boolean ddd = (x & 1) == 1;//奇数
    // boolean ddd2 = (x & 1) == 0;//偶数

    // int bb = x >> 1;// x/2

    // x <<= 1;

    // int n = 26;
    // int reverse = 0;
    // for (int i = 0; i < 5; i++) {
    //     reverse = reverse << 1;
    //     System.out.println(reverse);
    //     reverse = reverse + (n & 1);//n&1 = 取n的最后一位
    //     n >>= 1;
    // }

    // int[] arr = new int[] { 1, 4, 3, 6 };
    // int left = 0;
    // int right = arr.length - 1;
    // //QuickSort.quickSort(arr, left, right);
    // //MergeSort.mergeSort(arr, left, right);
    // HeapSort.heapSort(arr);

    // System.out.println(7);

    // final App multiThread1 = new App();
    // final App multiThread2 = new App();

    // new Thread(new Runnable() {
    //     public void run() {
    //         multiThread1.printNum("thread1", "a");
    //     }
    // }).start();

    // Thread.sleep(5000);
    // System.out.println("等待5秒，确保thread1已经执行完毕！");

    // new Thread(new Runnable() {
    //     public void run() {
    //         multiThread2.printNum("thread2", "b");
    //     }
    // }).start();

    // int[] nums = { 1, 1, 2 };
    // App.removeDuplicates(nums);
  }


}


